#ifndef _MUTABLE_DOUBLE_LIST_HPP_
#define _MUTABLE_DOUBLE_LIST_HPP_
#include "MutableContainer.hpp"

template<typename E>
class MutableDoubleList;

template<typename E>
class DoubleLinkNode
{
    friend class MutableDoubleList<E>;
private:
    E ele;
    DoubleLinkNode<E>* pre;
    DoubleLinkNode<E>* next;
public:
    DoubleLinkNode(E ele);
};

template<typename E>
inline DoubleLinkNode<E>::DoubleLinkNode(E ele)
{
    this->ele = ele;
    pre = nullptr;
    next = nullptr;
}



template<typename E>
class MutableDoubleList : public MutableContainer<E>
{
private:
    DoubleLinkNode<E> * head;
    DoubleLinkNode<E> * tail;
    int len;  //数量

public:
    MutableDoubleList();
    ~MutableDoubleList() override;

    /* 在末尾添加元素 */
    void add(E ele)override;
    /* 在指定下标添加一个元素 */
    void add(int index, E ele)override;
    /* 按照下标删除元素 */
    E remove(int index)override;
    /* 按照元素进行删除 */
    bool removeElement(E ele)override;
    /* 清空容器 */
    void clear()override;
    /* 通过下标修改元素 */
    E set (int index, E ele)override;
    /* 通过下标获取元素 */
    E get(int index)override;
    /* 排序 */
    void sort()override;
    /* 查找元素出现的下标 */
    int index(E ele)override;
    /* 将容器中的元素拼接成字符串 */
    string str()override;    
    /* 获取元素个数 */
    int length()override;

};

template <typename E>
inline MutableDoubleList<E>::MutableDoubleList()
{
    head = nullptr;
    tail = nullptr;
    len = 0;
}

template <typename E>
inline int MutableDoubleList<E>::length()
{
    return len;
}

/* 在末尾添加元素 */
template <typename E>
inline void MutableDoubleList<E>::add(E ele)
{
    DoubleLinkNode<E> * tmp = new DoubleLinkNode<E>(ele);
    if(tail == nullptr)
    {
        head = tmp;
        tail = tmp;
    }
    else
    {
        tail->next = tmp;
        tmp->pre = tail;
        tail = tmp;
    }

    len++;
}
/* 在指定下标添加一个元素 */
template <typename E>
inline void MutableDoubleList<E>::add(int index, E ele)
{
    if(index <= 0 || index >= len)
    {
        exit(-1);
    }
    /* 算不算0呢？ */
    DoubleLinkNode<E> * tmp = new DoubleLinkNode<E>(ele);
    DoubleLinkNode<E> * travel = head;
    while(index != 0)
    {
        travel = travel->next;
        index--;
    }
    if(travel->pre != nullptr)
    {
        travel->pre->next = tmp;
    }
    tmp->pre = travel->pre;
    tmp->next = travel;
    travel->pre = tmp;
    len++;
}
/* 按照下标删除元素 */
template <typename E>
inline E MutableDoubleList<E>::remove(int index)
{   
    DoubleLinkNode<E> * tmp = head;
    while(index != 0)
    {
        tmp = tmp->next;
        index--;
    }
    if(tmp->pre != nullptr)
    {
        tmp->pre->next = tmp->next;
    }
    if(tmp->next != nullptr)
    {
        tmp->next->pre = tmp->pre;
    }
    tmp->pre = nullptr;
    tmp->next = nullptr;
    E Tmp = tmp->ele;
    delete tmp;
    len--;
    return Tmp;
}
/* 按照元素进行删除 */
template <typename E>
inline bool MutableDoubleList<E>::removeElement(E ele)
{
    DoubleLinkNode<E> * travel = head;
    int flag = 0;
    while(travel != nullptr)
    {
        if(travel->ele == ele)
        {
            flag = 1;
            break;
        }
        travel = travel->next;
    }
    if(flag)
    {
        if(travel->pre != nullptr)
        {
            travel->pre->next = travel->next;
        }
        if(travel->next != nullptr)
        {
            travel->next->pre = travel->pre;
        }
        travel->pre = nullptr;
        travel->next = nullptr;
        delete travel;
        len--;
        return true;
    }
    return false;
}
/* 清空容器 */
template <typename E>
inline void MutableDoubleList<E>::clear()
{
    /* 销毁链表前先释放每一个节点 */
    DoubleLinkNode<E> * tmp = nullptr;

    while(head != nullptr)
    {
        tmp = head;
        head = head->next;
        delete tmp;
    }
    len = 0;
}
/* 通过下标修改元素 */
template <typename E>
inline E MutableDoubleList<E>::set (int index, E ele)
{
    if(index < 0 || index >= len)
    {
        exit(-1);
    }
    DoubleLinkNode<E> * travel = head;
    while(index != 0)
    {
        travel = travel->next;
        index--;
    }
    E tmp = travel->ele;
    travel->ele = ele;
    return tmp;
}
/* 通过下标获取元素 */
template <typename E>
inline E MutableDoubleList<E>::get(int index)
{
    if(index < 0 || index >= len)
    {
        exit(-1);
    }
    DoubleLinkNode<E> * travel = head;
    while(index != 0)
    {
        travel = travel->next;
        index--;
    }
    return travel->ele;
}
/* 排序 */
template <typename E>
inline void MutableDoubleList<E>::sort()
{

}
/* 通过元素获取下标 */
template <typename E>
inline int MutableDoubleList<E>::index(E ele)
{
    int pos = 0;
    DoubleLinkNode<E> * travel = head;
    while(travel != nullptr)
    {
        if(travel->ele == ele)
        {
            return pos;
        }
        travel = travel->next;
        pos++;
    }
    return -1;
}
/* 将容器中的元素拼接成字符串 */
template <typename E>
inline string MutableDoubleList<E>::str()
{
    if(len == 0)
    {
        return "[]";
    }
    /* 创建一个ostringstream的对象，用来拼接元素 */
    ostringstream oss;
    oss << "[";
    DoubleLinkNode<E> * tmp = head;
    while(tmp != tail)
    {
        oss << tmp->ele << ",";
        tmp = tmp->next;
    }
    oss << tmp->ele << "]";

    return oss.str();
}   

/* 析构函数 */
template <typename E>
inline MutableDoubleList<E>::~MutableDoubleList()
{
    MutableDoubleList<E>::clear();
}
#endif